我們正在建構什麼 🎯
- 資料結構： 一個 優先權佇列（PQ）。
- 它是一種抽象資料類型，類似於列表或佇列，但帶有特殊機制。
- 每個項目都有一個「優先權」（即鍵值）。
- 當你執行「取出」時，你總是總是取得優先權最高的項目。
- 操作方式：
- 1.
push(k) - 2.
peek() - 3.
pop()
- 1.
- 實作方式：我們將使用 二元最大堆積。
- 為什麼使用堆積？ 因為效率高！堆積可提供：
push: O(log N)pop: O(log N)peek: O(1)
什麼是最大堆積？
一種具有兩項簡單規則的二元樹：
1. 形狀性質
它是一棵 完整的二元樹。所有層級皆已填滿，僅最後一層可能未滿，且會從左至右填滿。中間不會出現空缺。沒有空缺。
點選葉節點以移除
2. 最大堆積性質
父節點的鍵值 大於等於 其子節點的鍵值。這確保了最 大的元素永遠位於根節點。
如何儲存樹狀結構 💾
由於這棵樹是 完整的，因此我們可以完美地以簡單陣列來儲存它。
索引運算（零起始）
當某節點位於索引 i 時：
- 父節點
(i - 1) // 2 - 左子節點
2 * i + 1 - 右子節點
2 * i + 2
建議： 請熟記這些公式！它們正是在陣列內導航「樹」結構的關鍵。